package cxydmmszl.chapter05.t089.middle1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 添加最少的字符使字符串整体都是回文串字符串
 * <li style="color: green;">Desc</li>
 * 给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，
 * 让 str 整体都是回文字符串的一种结果。
 * <li style="color: green;">Input</li>
 * 输入包含一行字符串，代表 str（1≤length(str)≤5000）。
 * <li style="color: green;">Output</li>
 * 输出一行，代表返回的字符串。
 * <li style="color: blue;">Link</li> CD124
 *
 * @author habitplus
 * @since 2021-09-12 12:26
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        br.close();

        s = solve(s);
        System.out.println(s);
    }

    private static String solve(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        char[] chs = s.toCharArray();
        int n = chs.length;
        // dp[i][j] 表示 s[i...j]至少添加多少字符才能变成回文串
        int[][] dp = new int[n][n];
        for (int j = 1; j < n; j++) {
            dp[j - 1][j] = chs[j] == chs[j - 1] ? 0 : 1;
            for (int i = j - 2; i >= 0; i--) {
                if (chs[j] == chs[i]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        char[] ans = new char[n + dp[0][n - 1]];

        int l = 0;
        int r = n - 1;
        int lpsL = 0;
        int lpsR = ans.length - 1;

        while (l <= r) {
            if (chs[l] == chs[r]) {
                ans[lpsL] = chs[l++];
                ans[lpsR] = chs[r--];
            } else if (dp[l][r - 1] > dp[l + 1][r]) {
                // 在 r右边 添加 chs[l]
                ans[lpsR] = chs[l];
                ans[lpsL] = chs[l++];
            } else {
                // 在 l左边 添加 chs[r]
                ans[lpsR] = chs[r];
                ans[lpsL] = chs[r--];
            }
            lpsL++;
            lpsR--;
        }
        return new String(ans);
    }
}
